package com.heima.leetcode.datastructure.hashtable;

import java.util.HashMap;

/**
 * <strong>获取当前字符串的最长字串的长度 3</strong>
 * <p>注：s 由英文字母、数字、符号和空格组成</p>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/26 9:45
 */
public class LongestSubstring {

    /**
     * <h3>方法一：hashMap O(N)</h3>
     * 遍历一次，存储字符位置，如果出现重复，则更新begin
     *
     * @param s 字符串
     * @return 最长字串
     */
    public static int lengthOfLongestSubstring1(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int begin = 0;
        int maxLength = 0;
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            Integer sameIndex = hashMap.get(c);
            if (sameIndex != null) {
                // 取出来的索引可能会比begin小，不能回头走，这种情况不行，所以取最大值
                begin = Math.max(sameIndex + 1, begin);
            }
            hashMap.put(c, end);
            maxLength = Math.max(maxLength, end - begin + 1);
        }
        return maxLength;
    }

    /**
     * <h3>方法二：数组 O(N)</h3>
     * 用数组来存，字符对应ascii编码对应数组索引，字符串索引作为值存入
     * @param s 字符串
     * @return 最长字串的长度
     */
    public static int lengthOfLongestSubstring2(String s) {
        int[] array = new int[128];
        int begin = 0;
        int maxLength = 0;
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            int nextIndex = array[c];
            if (nextIndex != 0) {
                begin = Math.max(begin, nextIndex);
            }
            array[c] = end + 1;
            maxLength = Math.max(maxLength, end - begin + 1);
        }
        return maxLength;
    }
}
